# ๋ณํฉ ์ ๋ ฌ(Merge Sort)
ํฉ๋ณ ์ ๋ ฌ์ด๋ผ๊ณ ๋ ๋ถ๋ฅด๋ฉฐ, ๋ถํ ์ ๋ณต ๋ฐฉ๋ฒ์ ํตํด ๊ตฌํ
๋ถํ ์ ๋ณต์ด๋?
ํฐ ๋ฌธ์ ๋ฅผ ์์ ๋ฌธ์ ๋จ์๋ก ์ชผ๊ฐ๋ฉด์ ํด๊ฒฐํด๋๊ฐ๋ ๋ฐฉ์
๋น ๋ฅธ ์ ๋ ฌ๋ก ๋ถ๋ฅ๋๋ฉฐ, ํต์ํธ์ ํจ๊ป ๋ง์ด ์ธ๊ธ๋๋ ์ ๋ ฌ ๋ฐฉ์์ด๋ค.
ํต์ํธ์๋ ๋ฐ๋๋ก ์์ ์ ๋ ฌ
์ ์ํจ
์๊ฐ๋ณต์ก๋
ํ๊ท | ์ต์ | ์ต์ |
---|---|---|
ฮ(nlogn) | ฮฉ(nlogn) | O(nlogn) |
์์๋ฅผ ์ชผ๊ฐ ํ, ๋ค์ ํฉ๋ณ์ํค๋ฉด์ ์ ๋ ฌํด๋๊ฐ๋ ๋ฐฉ์์ผ๋ก, ์ชผ๊ฐ๋ ๋ฐฉ์์ ํต์ ๋ ฌ๊ณผ ์ ์ฌ
- mergeSort
public void mergeSort(int[] array, int left, int right) {
if(left < right) {
int mid = (left + right) / 2;
mergeSort(array, left, mid);
mergeSort(array, mid+1, right);
merge(array, left, mid, right);
}
}
์ ๋ ฌ ๋ก์ง์ ์์ด์ merge() ๋ฉ์๋๊ฐ ํต์ฌ
ํต์ํธ์์ ์ฐจ์ด์
ํต์ ๋ ฌ : ์ฐ์ ํผ๋ฒ์ ํตํด ์ ๋ ฌ(partition) โ ์์ญ์ ์ชผ๊ฐฌ(quickSort)
ํฉ๋ณ์ ๋ ฌ : ์์ญ์ ์ชผ๊ฐค ์ ์์ ๋งํผ ์ชผ๊ฐฌ(mergeSort) โ ์ ๋ ฌ(merge)
- merge()
public static void merge(int[] array, int left, int mid, int right) {
int[] L = Arrays.copyOfRange(array, left, mid + 1);
int[] R = Arrays.copyOfRange(array, mid + 1, right + 1);
int i = 0, j = 0, k = left;
int ll = L.length, rl = R.length;
while(i < ll && j < rl) {
if(L[i] <= R[j]) {
array[k] = L[i++];
}
else {
array[k] = R[j++];
}
k++;
}
// remain
while(i < ll) {
array[k++] = L[i++];
}
while(j < rl) {
array[k++] = R[j++];
}
}
์ด๋ฏธ ํฉ๋ณ์ ๋์์ด ๋๋ ๋ ์์ญ์ด ๊ฐ ์์ญ์ ๋ํด์ ์ ๋ ฌ์ด ๋์ด์๊ธฐ ๋๋ฌธ์ ๋จ์ํ ๋ ๋ฐฐ์ด์ ์์ฐจ์ ์ผ๋ก ๋น๊ตํ๋ฉด์ ์ ๋ ฌํ ์๊ฐ ์๋ค.
โ โ โ ํฉ๋ณ์ ๋ ฌ์ ์์ฐจ์ ์ธ ๋น๊ต๋ก ์ ๋ ฌ์ ์งํํ๋ฏ๋ก, LinkedList์ ์ ๋ ฌ์ด ํ์ํ ๋ ์ฌ์ฉํ๋ฉด ํจ์จ์ ์ด๋ค.โ โ โ
LinkedList๋ฅผ ํต์ ๋ ฌ์ ์ฌ์ฉํด ์ ๋ ฌํ๋ฉด?
์ฑ๋ฅ์ด ์ข์ง ์์
ํต์ ๋ ฌ์, ์์ฐจ ์ ๊ทผ์ด ์๋ ์์ ์ ๊ทผ์ด๊ธฐ ๋๋ฌธ
LinkedList๋ ์ฝ์ , ์ญ์ ์ฐ์ฐ์์ ์ ์ฉํ์ง๋ง ์ ๊ทผ ์ฐ์ฐ์์๋ ๋นํจ์จ์ ์
๋ฐ๋ผ์ ์์๋ก ์ ๊ทผํ๋ ํต์ํธ๋ฅผ ํ์ฉํ๋ฉด ์ค๋ฒํค๋ ๋ฐ์์ด ์ฆ๊ฐํ๊ฒ ๋จ
๋ฐฐ์ด์ ์ธ๋ฑ์ค๋ฅผ ์ด์ฉํด์ ์ ๊ทผ์ด ๊ฐ๋ฅํ์ง๋ง, LinkedList๋ Head๋ถํฐ ํ์ํด์ผ ํจ
๋ฐฐ์ด[O(1)] vs LinkedList[O(n)]
private void solve() {
int[] array = { 230, 10, 60, 550, 40, 220, 20 };
mergeSort(array, 0, array.length - 1);
for (int v : array) {
System.out.println(v);
}
}
public static void mergeSort(int[] array, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(array, left, mid);
mergeSort(array, mid + 1, right);
merge(array, left, mid, right);
}
}
public static void merge(int[] array, int left, int mid, int right) {
int[] L = Arrays.copyOfRange(array, left, mid + 1);
int[] R = Arrays.copyOfRange(array, mid + 1, right + 1);
int i = 0, j = 0, k = left;
int ll = L.length, rl = R.length;
while (i < ll && j < rl) {
if (L[i] <= R[j]) {
array[k] = L[i++];
} else {
array[k] = R[j++];
}
k++;
}
while (i < ll) {
array[k++] = L[i++];
}
while (j < rl) {
array[k++] = R[j++];
}
}